package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * LCP 34. 二叉树染色
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/12 22:03
 */
public class MaxValue {

    private int k;

    public int maxValue(TreeNode root, int k) {
        this.k = k;
        int[] arr = find(root);
        int m = 0;
        for (int i = 0; i <= k; i++) {
            m = Math.max(m, arr[i]);
        }
        return m;
    }

    private int[] find(TreeNode node) {
        if (node == null) {
            return new int[k + 1];
        }
        int[] ls = find(node.left);
        int[] rs = find(node.right);
        int[] arr = new int[k + 1];
        int m = 0;
        for (int i = 0; i <= k; i++) {
            m = Math.max(m, ls[i]);
        }
        int n = 0;
        for (int i = 0; i <= k; i++) {
            n = Math.max(n, rs[i]);
        }
        arr[0] = m + n;
        for (int i = 1; i <= k; i++) {
            int max = 0;
            for (int j = 0; j < i; j++) {
                max = Math.max(max, ls[j] + rs[i - j - 1]);
            }
            arr[i] = max + node.val;
        }
        return arr;
    }

}
